package com.zk.algorithm.array;

import com.zk.algorithm.annotation.Finished;
import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.HashSet;
import java.util.Set;

/**
 * Input: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}
 Output: 5
 The subsequence 36, 35, 33, 34, 32 is the longest subsequence
 of consecutive elements.

 那几个数字都连续，一直连着
 *
 * @author zk
 */
@Hard
@LeetCodeExplore
@Finished(false)
public class LongestConsecutiveSubsequence {

    public int longestConsecutive(int[] nums) {
        // ===========================
        // 注意这个地方，直接转为 Set 的方法并没有，只能 for 循环
        // ===========================
        Set<Integer> set = fromArray(nums);
        int ans = 0;

        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int y = num + 1;

                while (set.contains(y)) {
                    y++;
                }

                ans = Math.max((y - num), ans);
            }
        }

        return ans;
    }

    private Set<Integer> fromArray(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num: nums) {
            set.add(num);
        }

        return set;
    }

}
